package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-11-15 10:53
 * @description: Functions of this class is
 * 官方题解 O（1）：
 * 关键公式：a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
 * 解释:设链表中环外部分的长度为 aslow 指针进入环后，又走了 b 的距离与fast 相遇。
 * 此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc.
 *
 * public ListNode detectCycle(ListNode head) {
 *         if(head==null||head.next==null){
 *             return null;
 *         }
 *         ListNode slow=head;
 *         ListNode fast=head;
 *         while(fast!=null&&fast.next!=null){
 *             slow=slow.next;
 *             fast=fast.next.next;
 *             if(fast==slow){//说明形成环了
 *                 ListNode p=head;//设置一个新的指针，从头开始
 *                 while(p!=slow){//然后直到和slow相遇，则找到了相遇点（数学公式可证）
 *
 *                     slow=slow.next;
 *                     p=p.next;
 *                 }
 *                 return p;
 *             }
 *         }
 *         return null;
 *     }
 **/
public class NoNo环形链表II {
    public static void main(String[] args) {

    }
    /**
     * 我自己的哈希表做法:。。。。。。。
     * public ListNode detectCycle(ListNode head) {
     *         HashSet<ListNode> set=new HashSet<ListNode>();
     *         while(head!=null){
     *             if(set.contains(head)){
     *                 return head;
     *             }
     *             set.add(head);
     *             head=head.next;
     *         }
     *         return null;
     *     }
     */
}